<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        - 在类里，声明一个数组，用来装元素
        - 主要方法：插入、删除堆顶、获取堆顶、获取堆大小

        插入
        - 将值插入堆的底部，即数组的尾部
        - 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
        - 大小为k的堆中插入元素的时间复杂度为 O(logk) 取决于树的高度

        删除堆顶
        - 用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)
        - 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
        - 大小为k的堆中删除堆顶的时间复杂度为O(logk)

        获取堆顶和堆的大小
        - 获取堆顶：返回数组的头部
        - 获取堆的大小：返回数组的长度

     -->
</head>
<body>
    <script>
        class MinHeap {
            constructor() {
                this.heap = [];
            }
            // 交换两个节点
            swap(i1, i2) {
                const temp = this.heap[i1];
                this.heap[i1] = this.heap[i2];
                this.heap[i2] = temp;
            }
            // 获取父节点
            getParentIndex(i) {
                return (i - 1) >> 1; // 相当于 Math.floor((i-1) / 2);
            }
            // 获取左子节点
            getLeftIndex(i) {
                return i * 2 + 1;
            }
            getRightIndex(i) {
                return i * 2 + 2;
            }
            // 上移操作
            shiftUp(index) {
                if (index == 0) { return; } // 如果已经是根节点，就不用再上移了
                const parentIndex = this.getParentIndex(index);
                if (this.heap[parentIndex] > this.heap[index]) {
                    this.swap(parentIndex, index);
                    this.shiftUp(parentIndex)
                }
            }
            // 下移操作
            shiftDown(index) {
                const leftIndex = this.getLeftIndex(index);
                const rightIndex = this.getRightIndex(index);
                if (this.heap[leftIndex] < this.heap[index]) {
                    this.swap(leftIndex, index);
                    this.shiftDown(leftIndex);
                }
                if (this.heap[rightIndex] < this.heap[index]) {
                    this.swap(rightIndex, index);
                    this.shiftDown(rightIndex);
                }
            }
            // 插入
            insert(value) {
                this.heap.push(value);
                this.shiftUp(this.heap.length - 1);
            }
            // 删除堆顶
            pop() {
                this.heap[0] = this.heap.pop();  // 删除最后一个元素并把值赋值给堆顶，就相当于堆顶和最后一个元素交换再删除它
                this.shiftDown(0);
            }
            // 获取堆顶
            peek() {
                return this.heap[0];
            }
            // 获取堆的大小
            size() {
                return this.heap.length;
            }
        }

        const h = new MinHeap();
        h.insert(3);
        h.insert(2);
        h.insert(1);
        h.pop();
    </script>
</body>
</html>